// https://leetcode.cn/problems/majority-element/description/?envType=study-plan-v2&envId=top-100-liked
// 169. 多数元素
// 简单
// 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
// 你可以假设数组是非空的，并且给定的数组总是存在多数元素。

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  // 这道题目不需要借助 hash 表就可以实现

  // 如果你把这个众数元素想象成正电粒子，其他的所有元素都想象成负电粒子，那么它们混合起来会怎样？
  // 在正负粒子混合的过程中，整体的带电性可能在正负间波动，但最终的结果一定是正电。

  // 要寻找的众数是 target
  let target = nums[0]
  // cnt 类比带电粒子中的带电性
  let cnt = 0
  for (const n of nums) {
    // 当计数器为 0 假定当前数就是目标众数
    if (cnt === 0) {
      target = n
    } else if (n === target) {
      // 如果碰到众数累加计数器
      ++cnt
    } else {
      // 如果碰到其他数，相当于抵消了，减少计数器
      --cnt
    }
  }

  // 此时的 count 必然大于 0，因为不相同的数都被抵消了
  // 此时的 target 必然就是目标众数
  return target
}

console.log(
  majorityElement([1, 1, 2, 2, 3, 3, 4, 4, 4])
)
